package JavaLab.Collections;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyHashMap implements MyMap{
	static final int MAXIMUM_CAPACITY = 1 << 30;
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int capacity;
    private float loadFactor;
    private int size;

    private SimpleEntry[] table;

    public MyHashMap(){
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public MyHashMap(int initialCapacity) throws IllegalArgumentException{
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public MyHashMap(int initialCapacity, float loadFactor) throws  IllegalArgumentException{
        if(initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                                initialCapacity);
        if(initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if(loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor +" +
                                                loadFactor);

        this.capacity = initialCapacity;
        this.loadFactor = loadFactor;

        this.table = new SimpleEntry[capacity];
    }

    public void clear() {
        Arrays.fill(table, null);
        size = 0;
    }

    public boolean containsKey(Object key) {
        return get(key) != null;
    }

    public boolean containsValue(Object value) {
        if(value == null){
            for(int i = 0; i < table.length; i++)
                for (SimpleEntry e = table[i]; e != null; e = e.next)
                    if(e.value == null)
                        return true;
            return false;
        }

        for(int i = 0; i < table.length; i++)
            for(SimpleEntry e = table[i]; e != null; e = e.next)
                if(e.value.equals(value))
                    return true;
        return false;
    }

    public Object get(Object key) {
        if(size == 0)
            return null;
        int hash = (key == null) ? 0 : key.hashCode();
        for(SimpleEntry e = table[indexFor(hash, table.length)]; e != null; e = e.next){
            Object k = null;
            if(e.hash == hash &&
                    (k = e.key) == key || (key != null && key.equals(k)))
                return e.value;
        }
        return null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Object put(Object key, Object value) {
        int hash = key.hashCode();
        int i = indexFor(hash, table.length);
        for(SimpleEntry e = table[i]; e != null; e = e.next){
            Object k = null;
            if(e.hash == hash && ((k = e.key) == key || key.equals(k))){
                Object oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        addEntry(hash, key, value, i);
        return null;
    }

    void addEntry(int hash, Object key, Object value, int bucketIndex){
        if(size >= capacity * loadFactor && table[bucketIndex] != null){
            resize(2 * table.length);
            hash = (key != null) ? key.hashCode() : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     */
    void resize(int newCapacity){
        SimpleEntry[] newTable = new SimpleEntry[newCapacity];
        transfer(newTable);
        table = newTable;
    }

    /**
     * Transfers all SimpleEntries from current table to newTable
     */
    void transfer(SimpleEntry[] newTable){
        int newCapacity = newTable.length;
        for(SimpleEntry e : table){
            while(e != null){
                SimpleEntry next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

    void createEntry(int hash, Object key, Object value, int bucketIndex){
        SimpleEntry e = table[bucketIndex];
        table[bucketIndex] = new SimpleEntry(hash, key, value, e);
        size++;
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    public Object remove(Object key) {
        if(size == 0)
            return null;

        int hash = (key == null) ? 0: key.hashCode();
        int i = indexFor(hash, table.length);
        SimpleEntry prev = table[i];
        SimpleEntry e = prev;

        while(e != null){
            SimpleEntry next = e.next;
            Object k;
            if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))){
                size--;
                if(prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

    public int size() {
        return size;
    }

    public Iterator entryIterator() {
        return new EntryIterator();
    }

    static int indexFor(int h, int length){
        return h & (length - 1);
    }

    public class SimpleEntry implements MyMap.Entry{
        final Object key;
        Object value;
        SimpleEntry next;
        int hash;

        SimpleEntry(int h, Object k, Object v, SimpleEntry n){
            key = k;
            value = v;
            next = n;
            hash = h;
        }

        public Object getKey() {
            return key;
        }

        public Object getValue() {
            return value;
        }

        public Object setValue(Object value) {
            Object oldValue = value;
            this.value = value;
            return  oldValue;
        }
    }

    private final class EntryIterator implements Iterator{
        SimpleEntry next;
        int index;
        SimpleEntry current;

        public boolean hasNext() {
            return next != null;
        }

        public SimpleEntry next() {
            SimpleEntry e = next;
            if(e == null)
                throw new NoSuchElementException();

            current = e;
            return e;
        }

        public void remove() {
            if(current == null)
                throw new IllegalStateException();
            Object k = current.key;
            current = null;
            MyHashMap.this.remove(k);
        }
    }
}
